package com.jdaw.datastructure.sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr={-9,78,0,23,-567,70,-8};
        quickSort(arr,0,6);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int left,int right){
        int l=left;
        int r=right;
        int pivot=arr[(l+r)/2];
        int temp=0;
        while(l<r){
            //在pivot的左边一直找大于pivot的
           while(arr[l]<pivot){
                l+=1;
           }
            while(arr[r]>pivot){
                r-=1;
            }
            //如果有l>=r,则说明排序已完成
            if(l>=r){
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //如果左边有元素已经等于中间了，那么说明，右边没有要和左边换的了
            if(arr[l]==pivot){
                r-=1;
            }
            //右边同理
            if(arr[r]==pivot){
                l+=1;
            }
        }
        //防止栈溢出
        if(r==l){
            r--;//让r去左边，为左递归做准备
            l++;//让l去右边，为右递归做准备
        }
        //左递归
        if(left<r){
            quickSort(arr,left,r);
        }
        //右递归
        if(right>l){
            quickSort(arr,l,right);
        }
    }
}
